\chapter{Не быстрые сортировки}

Лекция (читай <<не лекция>>) от 23 сентября 2011 года

\subsection{Не быстрый quick sort}

Идея алгоритма быстрой сортировки, как и идеи очень многих других алгоритмов, основана на принципе <<разделяй и властвуй>>. В чем же особенность? А собственно в том, что все основные действия происходят во время разделения.

\begin{lstlisting}
QuickSort (A, p, r)
	q = Partition(A, p, r)
	QuickSort(A, p, q-1)
	QuickSort(A, q+1, r)
\end{lstlisting}

Как вы уже поняли, вся фишка алгоритма заключается в процедуре разделений (ну блин, я это поторяю, для тех кто думает медленно, а читает быстро). Задачи процедуры разделения:
\begin{itemize}
\item выбрать опорный элемент $x$

\item расположить элементы массива таким образом, что бы $\forall a \le x \left[ pos \left(a\right) < pos \left(x\right) \right]$
\end{itemize}

Очеидно, что далее мы просто сортируем каждую половинку. Но вот вопрос, полоинку ли, очевидно, что скорость сортировки зависит и очень сильно от выбора опорного элемента, и не трудно придумать случай, когда сортировка потребует квадратичного времени работы, но здесь мы рассмотрим почему же в среднем случа она се-таки работает за $n \log n$, постараемся избегать разяснений на пальцах.

Чтобы дело пошло веселее, посмотрим как может выглядеть процедура разделения:

\begin{lstlisting}
Partition (A, p, r)
	i=p-1
	for j = p to r-1
		if A[j] < A[r]
			swap (A[j], A[i+1])
			i++
	swap (A[r], A[i+1])
	return i+1
\end{lstlisting}

Основная операция в данном случае заключена в условном операторе, нетрудно опять же понять, что число любых операций сравнимо с числом операций сравнения (любых, имеется виду сравнений). Число сравнений зависит от размера разделяемого массива, покажем что имеется ввиду:
\[
	\begin{split}
		& A : [ a_1 | a_2 | ...  | ...  |  ...  | a_{n-1} | a_n ] \\
		& A': [ a_1' | a_2' | ... | ... | a_i' | ... | a_j' | ... | ... | a_{n-1}' | a'_n ]
	\end{split}
\]
Массив $A'$ - отсортированный массив, в этом случае можно заметить, что элементы $a'_i$ и $a'_j$ сравнивались только в том случае, если на каком-то этапе они являлись границами разделяемого массива, вероятность того, что эти элементы были границами разделяемого массива $P = \frac{2}{j-i+1}$ (ну это более или менее понятно), ну посчитаем все вместе (просуммируем все вероятности):
\[
	E\left(n\right) = \sum_{1 \le i < j \le n} \frac{2}{j-i+1} = 2 \sum_{i=1}^{n-1} \sum_{j=i+1}^{n} \frac{1}{j-i+1} \le 2 \sum_{i=1}^n \log n = 2n\log n
\]

\paragraph{Примечание.} 
\[
	1 + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \frac{1}{5} + .. + \frac{1}{n} < 1 + \frac{1}{2} + \frac{1}{2} + \frac{1}{4} + \frac{1}{4} + \frac{1}{4} + \frac{1}{4} + ... \approx \log_2 n
\]

\paragraph{Примечание.}
$E\left(n\right)$ - математическое ожидание числа сравнений, т. е. $E\left(n\right) = \sum \left[1 \cdot P\left(i cmp j\right) + 0 \cdot P\left(i not cmp j \right)\right]$ и суммирование происходит по всем парам $i$ и $j$

Есть и другой способ анализа среднего времени работы, что называется <<в лоб>>, для этого запишем реккурентное соотношение описывающе процедуру сортировку:
\[
	\begin{split}
		& T\left(n\right) = O \left(n\right) + \frac{1}{n} \sum_{i=1}^n \left[T\left(i-1\right) + T\left(n-i-1\right) \right] \le \\
		& \le an + \frac{1}{n} \sum_{i=1}^{n} \left[c\left(i-1\right)\log \left(i-1\right) + c\left(n-i-1\right)\log \left(n-i-1\right)\right]  = \\
		& = an + \frac{1}{n} \sum_{i=1}^n \left[cn \log \left(\left(i-1\right)\left(n-i-1\right)\right)\right]
	\end{split}
\]
